//#define _CRT_SECURE_NO_WARNINGS 1
//#include <stdio.h>
//
//#define MAX_VERTEX_NUM 20                   //�����������
//#define VRType int                          //��ʾ����Ȩֵ������
//#define VertexType int                      //ͼ�ж������������
//#define INFINITY 100000
//
//typedef struct {
//    VertexType vexs[MAX_VERTEX_NUM];        //�洢ͼ�ж�������
//    VRType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //��ά���飬��¼����֮��Ĺ�ϵ
//    int vexnum, arcnum;                      //��¼ͼ�Ķ������ͻ����ߣ���
//}MGraph;
//
//typedef int Path_Vertex[MAX_VERTEX_NUM];     //���ڴ洢���·���о����Ķ�����±�
//typedef int ShortPathTable[MAX_VERTEX_NUM]; //���ڴ洢�������·����Ȩֵ��
//
////���ݶ��㱾�����ݣ��жϳ������ڶ�ά�����е�λ��
//int LocateVex(MGraph* G, VertexType v) {
//    int i = 0;
//    for (; i < G->vexnum; i++) {
//        if (G->vexs[i] == v) {
//            break;
//        }
//    }
//    //����Ҳ����������ʾ��䣬����-1
//    if (i > G->vexnum) {
//        printf("no such vertex\n");
//        return -1;
//    }
//    return i;
//}
////����������
//void CreateUDG(MGraph* G) {
//    printf("Input the vex nums and arc nums :");
//    scanf_s("%d,%d", &(G->vexnum), &(G->arcnum));
//    for (int i = 0; i < G->vexnum; i++) {
//        printf("Input the vertexes:");
//        scanf_s("%d", &(G->vexs[i]));
//    }
//    for (int i = 0; i < G->vexnum; i++) {
//        for (int j = 0; j < G->vexnum; j++) {
//            G->arcs[i][j] = INFINITY;  //�Ƚ����ĳ�ʼ������Ϊ����
//        }
//    }
//    for (int i = 0; i < G->arcnum; i++) {
//        int v1, v2, w;
//        printf("Input the arc of two vertexes and the weight:");
//        scanf_s("%d,%d,%d", &v1, &v2, &w);
//        int n = LocateVex(G, v1);  //�ҵ���Ӧ��λ��
//        int m = LocateVex(G, v2);
//        if (m == -1 || n == -1) {
//            printf("no this vertex\n");
//            return;
//        }
//        G->arcs[n][m] = w;  //����Ӧλ�õ�Ȩ�ظ�ֵ
//    }
//}
//
//void ShortestPath_Dijkstra(MGraph G, int v0, Path_Vertex* p, ShortPathTable* D) {
//    int final[MAX_VERTEX_NUM];//���ڴ洢�������Ƿ��Ѿ�ȷ�����·��������
//    //�Ը�������г�ʼ��
//    for (int v = 0; v < G.vexnum; v++) {
//        final[v] = 0;
//        (*D)[v] = G.arcs[v0][v];   //��v0�ĸ����ߵ�Ȩֵ��ֵ��D��
//        (*p)[v] = 0;
//    }
//    //������v0λ�±�Ķ���Ϊ��ʼ�㣬���Բ������ж�
//    (*D)[v0] = 0;   //��ʼ������Դ������Ϊ0
//    final[v0] = 1;  //����Ϊ1����ʾ�����ڽ����������·��
//    int k = 0;
//    for (int i = 0; i < G.vexnum; i++) {
//        int min = INFINITY;
//        //ѡ�񵽸�����Ȩֵ��С�Ķ��㣬��Ϊ������ȷ�����·���Ķ���
//        for (int w = 0; w < G.vexnum; w++) {
//            if (!final[w]) {  //û��ȷ�����·������ȷ��
//                if ((*D)[w] < min) {
//                    k = w;   //�����Ӧ��Ȩֵ
//                    min = (*D)[w];
//                }
//            }
//        }
//        //���øö���ı�־λΪ1�������´��ظ��ж�
//        final[k] = 1;
//        //��v0���������Ȩֵ���и���
//        for (int w = 0; w < G.vexnum; w++) {
//            if (!final[w] && (min + G.arcs[k][w] < (*D)[w])) {
//                (*D)[w] = min + G.arcs[k][w];
//                (*p)[w] = k;//��¼�������·���ϴ��ڵĶ���
//            }
//        }
//    }
//}
//int main() {
//    MGraph G;
//    CreateUDG(&G);
//    Path_Vertex P;  //���·�������Ķ���
//    ShortPathTable D; //�洢���·��ֵ
//    ShortestPath_Dijkstra(G, 0, &P, &D);
//    for (int i = 1; i < G.vexnum; i++) {
//        if (D[i] != INFINITY) {
//            printf("V%d - V%dthe shortest path��", 0, i);
//            printf(" V%d <-", i);
//            int j = i;
//            //����ÿһ�����·���϶���¼�ž����Ķ��㣬���Բ���Ƕ�׵ķ�ʽ������ɵõ��������·���ϵ����ж���
//            while (P[j] != 0) {
//                printf(" V%d <-", P[j]);
//                j = P[j];
//            }
//            printf(" V0\n");
//        }
//        else {
//            printf("V%d - V%d have not the shortest path\n", 0, i);
//        }
//    }
//    printf("V%d to the every vertexes' distance:\n", 0);
//    for (int i = 1; i < G.vexnum; i++) {
//        if (D[i] == INFINITY) {
//            printf("V%d - V%d : have not path \n", G.vexs[0], G.vexs[i]);
//        }
//        else {
//            printf("V%d - V%d : %d \n", G.vexs[0], G.vexs[i], D[i]);
//        }
//    }
//    return 0;
//}

// function Kruskal(Graph G):
//     // 使用排序算法将边按照权重从小到大排序
//     sort(G.edges by weight)

//     Vexset = array of size G.V  // 初始化联通数组
//     for i from 0 to G.V - 1:
//         Vexset[i] = i

//     for i from 0 to G.E - 1:  // G.E 是边的数量
//         edge = G.edges[i]
//         v1 = LocateVex(G, edge.head)  // 找到边起点在顶点数组中的位置
//         v2 = LocateVex(G, edge.tail)  // 找到边终点在顶点数组中的位置
//         vs1 = Vexset[v1]
//         vs2 = Vexset[v2]

//         if vs1 != vs2:
//             // 打印边的信息
//             print(edge.head, edge.tail, edge.weight)

//             // 合并两个连通分量
//             for j from 0 to G.V - 1:
//                 if Vexset[j] == vs2:
//                     Vexset[j] = vs1

// end function

// function Prim(Graph G, Vertex u):
//     // 找到顶点 u 在图中的索引
//     k = LocateVex(G, u)
    
//     // 初始化 closedge 数组，closedge[j].lowcast 表示顶点 j 到集合 U 的最小边的权重
//     // closedge[j].adjvex 表示与顶点 j 相连的、权重最小的边的另一端点
//     for j from 0 to G.vexnum - 1:
//         closedge[j].adjvex = u
//         closedge[j].lowcast = G.arcs[k][j]
    
//     // 将 u 初始化为 U 的唯一成员，其最小边权重设置为 0
//     closedge[k].lowcast = 0
    
//     // 从 1 到 G.vexnum - 1 进行循环，每次将一个顶点并入 U
//     for i from 1 to G.vexnum - 1:
//         // 选择 closedge 中具有最小权重的顶点 k
//         k = MinCost(closedge, G.vexnum)
        
//         // u0 是最小边的一个顶点，属于 U；v0 是最小边的另一个顶点，属于 V-U
//         u0 = closedge[k].adjvex
//         v0 = G.vex[k]
        
//         // 输出边 (u0, v0) 及其权重
//         print(u0, " - ", v0, " : ", closedge[k].lowcast)
        
//         // 将顶点 k 并入 U
//         closedge[k].lowcast = 0
        
//         // 重新选择与新加入 U 的顶点相邻的最小边
//         for j from 0 to G.vexnum - 1:
//             if G.arcs[k][j] < closedge[j].lowcast:
//                 closedge[j].adjvex = G.vex[k]
//                 closedge[j].lowcast = G.arcs[k][j]
    
//     // 返回最小生成树的边集合
// end function
